package leetcode;

import list.LinkedListCreate;
import list.ListNode;

public class ReverseLinkedList {

	public static void main(String[] args) {
		ReverseLinkedList object = new ReverseLinkedList();
		int[] nums = {8, 6, 9, 5, 10, 7, 1};
		ListNode head = LinkedListCreate.createList(nums);
		head = object.reverseBetween2(head, 1, 4);
		LinkedListCreate.printList(head);
	}
	public ListNode reverseBetween(ListNode head, int m, int n) {
		if (head == null || head.next == null || n == m) {
			return head;
		}
		int length = 1;
		ListNode pre = new ListNode(0);
		pre.next = head;
		ListNode node = head;
		while(length < m){
			pre = node;
			node = node.next;
			length++;
		}
		ListNode[] res = reverseListNode(pre.next, n - m + 1);
		pre.next = res[0];
		return m == 1 ? pre.next : head;
	}

	// 返回反转之后的头结点的尾结点，ListNode[0]为头结点，ListNode[1]为尾结点
	public ListNode[] reverseListNode(ListNode head, int k) {
		if (head == null) {
			return new ListNode[] { head, null };
		} else {
			System.out.println("head: " + head.val);
		}
		// 首先判断以head开头的长度是否大于等于k
		int length = 1;
		ListNode node = head;
		ListNode tail = head;
		while (node.next != null && length < k) {
			node = node.next;
			tail = node;
			length++;
		}
		if (length < k) {
			return new ListNode[] { head, null };
		}
		ListNode linkNode = tail.next;

		// System.out.println("tail: " + tail.val + "linkNode:" + linkNode.val);
		node = head;
		ListNode pre = null;
		ListNode next = null;
		while (node != null && length > 0) {
			next = node.next;
			node.next = pre;
			pre = node;
			node = next;
			length--;
		}
		// 此时的head肯定为反转之后的尾结点
		head.next = linkNode;
		return new ListNode[] { pre, head };
	}
	
	/**
	 * 直接反转
	 */
	public ListNode reverseBetween2(ListNode head, int m, int n) {
		if (head == null || head.next == null || n == m) {
			return head;
		}
		int length = 1;
		ListNode preLinked = new ListNode(0);
		preLinked.next = head;
		ListNode nodeN = head;
		while(length < n){
			if(length == m - 1){
				preLinked = nodeN;
			}
			nodeN = nodeN.next;
			length++;
		}
		System.out.println("nodeN " + nodeN.val);
		
		ListNode tailLinked = nodeN.next;
		
		ListNode temp = preLinked.next;
		ListNode pre = null;
		ListNode next = null;
		while (temp != tailLinked) {
			next = temp.next;
			temp.next = pre;
			pre = temp;
			temp = next;
		}
		preLinked.next.next = tailLinked;
		preLinked.next = pre;
		
		return m == 1 ? preLinked.next : head;
	}
}
